0001    //
0002    //  BigUInt Shifts.swift
0003    //  BigInt
0004    //
0005    //  Created by Károly Lőrentey on 2016-01-03.
0006    //  Copyright © 2016 Károly Lőrentey. All rights reserved.
0007    //
0008    
0009    import Foundation
0010    
0011    //MARK: Shift Operators
0012    
0013    /// Shift a big integer to the right by `amount` bits and store the result in place.
0014    ///
0015    /// - Complexity: O(count)
0016    public func <<= (inout b: BigUInt, amount: Int) {
0017        typealias Digit = BigUInt.Digit
0018    
0019        precondition(amount >= 0)
0020        guard amount > 0 else { return }
0021    
0022        let ext = amount / Digit.width // External shift amount (new digits)
0023        let up = Digit(amount % Digit.width) // Internal shift amount (subdigit shift)
0024        let down = Digit(Digit.width) - up
0025    
0026        b.lift()
0027        if up > 0 {
0028            var i = 0
0029            var lowbits: Digit = 0
0030            while i < b.count || lowbits > 0 {
0031                let digit = b[i]
0032                b[i] = digit << up | lowbits
0033                lowbits = digit >> down
0034                i += 1
0035            }
0036        }
0037        if ext > 0 && b.count > 0 {
0038            b._digits.insertContentsOf(Array<Digit>(count: ext, repeatedValue: 0), at: 0)
0039            b._end = b._digits.count
0040        }
0041    }
0042    
0043    /// Shift a big integer to the left by `amount` bits and return the result.
0044    ///
0045    /// - Returns: b * 2^amount
0046    /// - Complexity: O(count)
0047    @warn_unused_result
0048    public func << (b: BigUInt, amount: Int) -> BigUInt {
0049        typealias Digit = BigUInt.Digit
0050    
0051        precondition(amount >= 0)
0052        guard amount > 0 else { return b }
0053    
0054        let ext = amount / Digit.width // External shift amount (new digits)
0055        let up = Digit(amount % Digit.width) // Internal shift amount (subdigit shift)
0056        let down = Digit(Digit.width) - up
0057    
0058        var result = BigUInt()
0059        if up > 0 {
0060            var i = 0
0061            var lowbits: Digit = 0
0062            while i < b.count || lowbits > 0 {
0063                let digit = b[i]
0064                result[i + ext] = digit << up | lowbits
0065                lowbits = digit >> down
0066                i += 1
0067            }
0068        }
0069        else {
0070            for i in 0..<b.count {
0071                result[i + ext] = b[i]
0072            }
0073        }
0074        return result
0075    }
0076    
0077    /// Shift a big integer to the right by `amount` bits and store the result in place.
0078    ///
0079    /// - Complexity: O(count)
0080    public func >>= (inout b: BigUInt, amount: Int) {
0081        typealias Digit = BigUInt.Digit
0082    
0083        precondition(amount >= 0)
0084        guard amount > 0 else { return }
0085    
0086        let ext = amount / Digit.width // External shift amount (new digits)
0087        let down = Digit(amount % Digit.width) // Internal shift amount (subdigit shift)
0088        let up = Digit(Digit.width) - down
0089    
0090        if ext >= b.count {
0091            b = BigUInt()
0092            return
0093        }
0094    
0095        b.lift()
0096    
0097        if ext > 0 {
0098            b._digits.removeRange(0 ..< ext)
0099            b._end = b._digits.count
0100        }
0101        if down > 0 {
0102            var i = b.count - 1
0103            var highbits: Digit = 0
0104            while i >= 0 {
0105                let digit = b[i]
0106                b[i] = highbits | digit >> down
0107                highbits = digit << up
0108                i -= 1
0109            }
0110            b.shrink()
0111        }
0112    }
0113    
0114    /// Shift a big integer to the right by `amount` bits and return the result.
0115    ///
0116    /// - Returns: b / 2^amount
0117    /// - Complexity: O(count)
0118    @warn_unused_result
0119    public func >> (b: BigUInt, amount: Int) -> BigUInt {
0120        typealias Digit = BigUInt.Digit
0121    
0122        precondition(amount >= 0)
0123        guard amount > 0 else { return b }
0124    
0125        let ext = amount / Digit.width // External shift amount (new digits)
0126        let down = Digit(amount % Digit.width) // Internal shift amount (subdigit shift)
0127        let up = Digit(Digit.width) - down
0128    
0129        if ext >= b.count { return BigUInt() }
0130    
0131        var result = BigUInt()
0132        if down > 0 {
0133            var highbits: Digit = 0
0134            for i in (ext..<b.count).reverse() {
0135                let digit = b[i]
0136                result[i - ext] = highbits | digit >> down
0137                highbits = digit << up
0138            }
0139        }
0140        else {
0141            for i in (ext..<b.count).reverse() {
0142                result[i - ext] = b[i]
0143            }
0144        }
0145        return result
0146    }
0147    
0148    
0149